Stirling numbers of the first kind

Stirling numbers of the first kind (often without the qualifying adjective signed) are given by

$s(n,k) = (-1)^{n-k} \left[{n \atop k}\right] .$

They are the coefficients in the expansion

$(x)_n = \sum_{k=0}^n s(n,k) x^k,$

where $(x)_n$ is the falling factorial

$(x)_n = x(x-1)(x-2)\cdots(x-n%2B1).$

Note that

$\left[{n \atop k}\right] = \left|s(n,k)\right| .$

Warning: the notations for signed and unsigned Stirling numbers are sometimes defined just the other way round.

Recurrence relation and table of values for the unsigned Stirling numbers

The unsigned Stirling numbers of the first kind can be calculated by the recurrence relation

$\left[{n%2B1\atop k}\right] = n \left[{n\atop k}\right] %2B \left[{n\atop k-1}\right]$

for $k > 0$ , with the initial conditions

$\left[{0\atop 0}\right] = 1 \quad\mbox{and}\quad \left[{n\atop 0}\right]=\left[{0\atop n}\right]=0$

for n > 0.

The above follows from the recurrence relation on the rising factorials:

$(x)^{(n%2B1)} = x(x%2B1)\cdots (x%2Bn-1)(x%2Bn)=n(x)^{(n)}%2Bx(x)^{(n)}.$

Below is a triangular array of unsigned values for the Stirling numbers of the first kind, similar in form to Pascal's triangle.

n \ k	0	1	2	3	4	5	6	7	8	9
0	1
1	0	1
2	0	1	1
3	0	2	3	1
4	0	6	11	6	1
5	0	24	50	35	10	1
6	0	120	274	225	85	15	1
7	0	720	1764	1624	735	175	21	1
8	0	5040	13068	13132	6769	1960	322	28	1
9	0	40320	109584	118124	67284	22449	4536	546	36	1

Simple identities

Note that although

$\left[{0 \atop 0}\right] = 1\quad\mbox{we have}\quad\left[{n\atop 0}\right] = 0\quad \mbox{if} \quad n > 0$

and

$\left[{0\atop k}\right] = 0\quad\mbox{if}\quad k > 0,\quad\mbox{or more generally,}\quad \left[{n\atop k}\right] = 0\quad\mbox{if}\quad k>n.$

Also

$\left[{n \atop 1}\right] = (n-1)!$

and

$\left[{n\atop n}\right] = 1, \quad \left[{n\atop n-1}\right] = {n \choose 2},$

and

$\left[{n\atop n-2}\right] = \frac{1}{4} (3n-1) {n \choose 3}\quad\mbox{ and }\quad\left[{n\atop n-3}\right] = {n \choose 2} {n \choose 4}.$

Similar relationships involving the Stirling numbers hold for the Bernoulli polynomials. Many relations for the Stirling numbers shadow similar relations on the binomial coefficients. The study of these 'shadow relationships' is termed umbral calculus and culminates in the theory of Sheffer sequences.

Combinatorial proofs

These identities may be derived by enumerating permutations directly. For example, how many permutations on [n] are there that consist of n − 3 cycles? There are three possibilities:

n − 6 fixed points and three two-cycles
n − 5 fixed points, a three-cycle and a two-cycle, and
n − 4 fixed points and a four-cycle.

We enumerate the three types, as follows:

choose the six elements that go into the two-cycles, decompose them into two-cycles and take into account that the order of the cycles is not important:

${n \choose 6} {6 \choose 2, 2, 2} \frac{1}{6}$

choose the five elements that go into the three-cycle and the two-cycle, choose the elements of the three-cycle and take into account that three elements generate two three-cycles:

${n \choose 5} {5 \choose 3} \times 2$

choose the four elements of the four-cycle and take into account that four elements generate six four-cycles:

${n \choose 4} \times 6.$

Sum the three contributions to obtain

${n \choose 6} {6 \choose 2, 2, 2} \frac{1}{6} %2B {n \choose 5} {5 \choose 3} \times 2 %2B {n \choose 4} \times 6 = {n \choose 2} {n \choose 4}.$

Other relations

These include

$\left[{n\atop 1}\right] = (n-1)!,$

$\left[{n\atop 2}\right] = (n-1)!\; H_{n-1},$

where H_n is a harmonic number, and

$\left[{n\atop 3}\right] = \frac{1}{2} (n-1)! \left[ (H_{n-1})^2 - H_{n-1}^{(2)} \right]$

$\left[{n\atop 4}\right] = \frac{1}{3!}(n-1)! \left[ (H_{n-1})^3 - 3H_{n-1}H_{n-1}^{(2)}%2B2H_{n-1}^{(3)} \right]$

where H_n^(m) is a generalized harmonic number. A generalization of this relation to harmonic numbers is given in a later section.

And we have also:

$\sum_{n=i}^\infty \frac{\left[{n\atop i}\right]}{n (n!)} = \zeta(i%2B1)$

where $\zeta(k)$ is the Riemann zeta function.

Generating function

A variety of identities may be derived by manipulating the generating function:

$H(z,u)= (1%2Bz)^u = \sum_{n=0}^\infty {u \choose n} z^n = \sum_{n=0}^\infty \frac{z^n}{n!} \sum_{k=0}^n s(n,k) u^k = \sum_{k=0}^\infty u^k \sum_{n=k}^\infty \frac {z^n}{n!} s(n,k) = e^{u\log(1%2Bz)}.$

In particular, the order of summation may be exchanged, and derivatives taken, and then z or u may be fixed.

Similarly, we may derive:

$G(z,u)= (1-z)^{-u} = \sum_{k=0}^\infty u^k \sum_{n=k}^\infty \frac {z^n}{n!} \left[{n\atop k}\right] = e^{u\log(1/(1-z))}.$

Finite sums

A simple sum is

$\sum_{k=0}^n \left[{n\atop k}\right] = n!$

or in a more general relationship,

$\sum_{k=0}^a \left[{n\atop k}\right] = n! - \sum_{k=0}^n \left[{n\atop k%2Ba%2B1}\right].$

The identity

$\sum_{p=k}^{n} {\left[{n\atop p}\right]\binom{p}{k}} = \left[{n%2B1\atop k%2B1}\right]$

can be proved by the techniques on the page Stirling numbers and exponential generating functions.

Infinite sums

Some infinite sums include

$\sum_{n=k}^\infty (-1)^{n-k} \left[{n\atop k}\right] \frac{z^n}{n!} = \frac{\left(\log (1%2Bz)\right)^k}{k!}$

where |z| < 1 (the singularity nearest to z = 0 of log(1 + z) is at z = −1.)

Explicit formula

The Stirling number s(n,n-p) can be found from the formula^[1]

$\begin{align} s(n,n-p) &= \frac{(n-1)!}{(n-p-1)!}\sum_{0 \leq k_1, \ldots , k_{p} \leq p} \left( \begin{array}{c} n%2BK-1\\K \end{array} \right) \left( \begin{array} {c} K \\ k_1, \ldots , k_p \end{array} \right) \delta_{p,\sum mk_m} \\ & ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ \times \left( \frac{-1~}{2!} \right)^{k_1} \left( \frac{-1~}{3!} \right)^{k_2} \cdots \left( \frac{-1}{(p%2B1)!} \right)^{k_p} , \end{align}$

where

$K =k_1 %2B \cdots %2B k_p,$

and

$\left( \begin{array}{c} K \\ k_1, \ldots , k_p \end{array} \right) \equiv \frac{ K!}{k_1! \cdots k_p!} ~ \delta_{K,k_1%2B \cdots %2B k_p}$

is a multinomial coefficient. The Kronecker delta in the first equation restricts the sums over the k's to a sum over the partitions of p.

Relation to harmonic numbers

Stirling numbers of the first kind can be expressed in terms of the harmonic numbers

$H^{(m)}_n=\sum_{k=1}^n \frac{1}{k^m}$

as follows:

$\left[{n \atop k}\right]= \frac{\Gamma(n)}{\Gamma(k)}w(n,k-1)$

where w(n, 0) = 1 and

$w(n,k)=\sum_{m=0}^{k-1}\frac{\Gamma(1-k%2Bm)}{\Gamma(1-k)}H_{n-1}^{(m%2B1)} w(n,k-1-m).$

In the above, $\Gamma(x)$ is the Gamma function.

Enumerative interpretation

The absolute value of the Stirling number of the first kind, s(n, k), counts the number of permutations of n objects with exactly k orbits (equivalently, with exactly k cycles). For example, s(4, 2) = 11, corresponds to the fact that the symmetric group on 4 objects has 3 permutations of the form

$(\bullet\bullet)(\bullet\bullet)$ —2 orbits of size 2 each

and 8 permutations of the form

$(\bullet\bullet\bullet)(\bullet)$ —1 orbit of size 3, and 1 orbit of size 1

(see the entry on cycle notation for the meaning of the above expressions.)

Let us prove this. First, we can remark that the unsigned Stirling numbers of the first kind are characterized by the following recurrence relation:

$| s(n%2B1,k)| = | s(n,k-1)| %2B n| s(n,k)|,\qquad 1\leq k < n.$

To see why the above recurrence relation matches the count of permutations with k cycles, consider forming a permutation of n + 1 objects from a permutation of n objects by adding a distinguished object. There are exactly two ways in which this can be accomplished. We could do this by forming a singleton cycle, i.e. leaving the extra object alone. This accounts for the s(n, k − 1) term in the recurrence formula. We could also insert the new object into one of the existing cycles. Consider an arbitrary permutation of n objects with k cycles, and label the objects a₁, ..., a_n, so that the permutation is represented by

$\displaystyle\underbrace{(a_1 \ldots a_{j_1})(a_{j_1%2B1} \ldots a_{j_2})\ldots(a_{j_{k-1}%2B1} \ldots a_n)}_{ k\ \mathrm{cycles}}.$

To form a new permutation of n + 1 objects and k cycles one must insert the new object into this array. There are, evidently n ways to perform this insertion. This explains the n s(n, k) term of the recurrence relation. Q.E.D.

References

^ J. Malenfant, "Finite, Closed-form Expressions for the Partition Function and for Euler, Bernoulli, and Stirling Numbers"

The Art of Computer Programming
Concrete Mathematics
M. Abramowitz, I. Stegun, ed (1972). "§24.1.3. Stirling Numbers of the First Kind". Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables (9th ed.). New York: Dover. p. 824.
Stirling numbers of the first kind, s(n,k) on PlanetMath.
Sloane's A008275 : Triangle read by rows of Stirling numbers of first kind. The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.

This article incorporates material from Stirling numbers of the first kind on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License.

Stirling numbers of the first kind

Contents

Definition

Unsigned Stirling numbers of the first kind